package com.wc.alorithm_blue_bridge._枚举.数列求和;

import java.util.LinkedList;

/**
 * @Author congge
 * @Date 2023/10/12 18:44
 * @description 数列求和
 * https://www.lanqiao.cn/problems/600/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=3
 */
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.fib(20190324));
    }

    public long fib(int n) {
        LinkedList<Long> queue = new LinkedList<>();

        for (int i = 0; i < 3; i++) {
            queue.add(1L);
        }

        n -= 3;
        while (n > 0) {
            long num1 = queue.get(0);
            long num2 = queue.get(1);
            long num3 = queue.get(2);
            queue.removeFirst();
            queue.add((num1 + num2 + num3)%10000);
            n--;
        }

        return queue.get(2);
    }
}
